#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:

    // 44. 通配符匹配
    // https://leetcode.cn/problems/wildcard-matching/
    bool isMatch(string s, string p) {
        int n1 = s.size(), n2 = p.size();
        vector<vector<bool>> dp(n1+1, vector<bool>(n2+1, false));
        dp[0][0] = true;
        for (int i = 1; i<=n2; ++i)
        {
            if (p[i-1] == '*')
                dp[0][i] = true;
            else
                break;
        }

        for (int i = 1; i<=n1; ++i)
        {
            for (int j = 1; j<=n2; ++j)
            {
                if (p[j-1] == '?')
                    dp[i][j] = dp[i-1][j-1];
                else if (p[j-1] == '*')
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                else 
                    dp[i][j] = s[i-1] == p[j-1] && dp[i-1][j-1];
            }
        }

        return dp[n1][n2];
    }

    // 10. 正则表达式匹配
    // https://leetcode.cn/problems/regular-expression-matching/
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m+1, vector<bool>(n+1));
        dp[0][0] = true;
        for (int j = 2; j<=n; j+=2)
        {
            if (p[j-1] == '*')
                dp[0][j] = true;
            else 
                break;
        }

        for (int i = 1; i<=m; ++i)
        {
            for (int j = 1; j<=n; ++j)
            {
                if (p[j-1] == '*')
                    dp[i][j] = dp[i][j-2] || (dp[i-1][j] && (p[j-2]==s[i-1] || p[j-2]=='.'));
                else 
                    dp[i][j] = (s[i-1] == p[j-1] || p[j-1] == '.') && dp[i-1][j-1];
            }
        }

        return dp[m][n];
    }
};